package com.wyx.suanfa;

import java.util.*;

/**
 * @author 王艺锡
 * @version 1.0
 */
public class LRUCache {
    //请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
    //实现 LRUCache 类：
    //LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
    //int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    //void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
    // 如果不存在，则向缓存中插入该组 key-value 。
    // 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    //函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache();
        lruCache.testA();
    }

    public void testA(){
        LinkedList<String> list = new LinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        test(list);
        System.out.println(list);
    }

    public void test(List<String> list){
        list.remove(0);
    }

}
/*
class LRUCache {
    //构建双向链表节点
    class DLinkedNode{
        private int key;
        private int value;
        private DLinkedNode prev;
        private DLinkedNode next;
        public DLinkedNode(){}
        public DLinkedNode(int _key,int _value){
            key = _key;
            value = _value;
        }
    }

    //存储缓存
    private Map<Integer,DLinkedNode> cache = new HashMap<>();
    //记录当前节点个数
    private int size;
    //最大容量
    private int capacity;
    //伪头结点
    private DLinkedNode head;
    //伪尾结点
    private DLinkedNode tail;

    //初始化构造器
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        //查询缓存是否存在key
        DLinkedNode node = cache.get(key);
        //如果存在，将节点移至头结点
        if(node != null){
            moveToHead(node);
            return node.value;
        }else{
            //如果不存在，返回-1
            return -1;
        }

    }

    //添加元素
    public void put(int key, int value) {
        //查询缓存节点是否已经存在
        DLinkedNode node = cache.get(key);
        //如果已经存在
        if(node != null){
            node.value = value;
            moveToHead(node);
        }else{
            //如果不存在
            node = new DLinkedNode(key,value);
            //添加至头结点
            addToHead(node);
            //添加到缓存
            cache.put(key,node);
            size++;
            //如果容量超出
            if(size > capacity){
                //删除尾结点
                DLinkedNode tailNode = removeTail();
                //删除尾结点缓存
                cache.remove(tailNode.key);
            }
        }

    }


    //删除节点
    private void removeNode(DLinkedNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    //添加至头结点
    private void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next = node;
        node.next.prev = node;
    }

    //移至头结点
    private void moveToHead(DLinkedNode node){
        //删除节点
        removeNode(node);
        //添加至头结点
        addToHead(node);
    }

    //删除尾结点
    private DLinkedNode removeTail(){
        DLinkedNode temp = tail.prev;
        removeNode(temp);
        return temp;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */